/*
	一致性哈希实现
*/

package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

// 用于依赖注入，自定义自己的Hash方法，默认采用crc32.ChecksumIEEE算法
type Hash func(data []byte) uint32

// 存储节点的数据结构Map
type Map struct {
	hash     Hash
	replicas int            // 每个真实节点对应的虚拟节点数量
	keys     []int          // 哈希环， 经过排序
	hashMap  map[int]string // 虚拟节点与真实节点的映射表
}

// 新建New
// hash为空则默认为crc32.ChecksumIEEE算法
func New(replicas int, fn Hash) *Map {
	m := &Map{
		hash:     fn,
		replicas: replicas,
		hashMap:  make(map[int]string),
	}

	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}

	return m
}

// 添加真实节点节点
func (m *Map) Add(keys ...string) {
	for _, key := range keys {

		// 对每个真实节点，将其转化为replicas个虚拟节点，计算hash后加入keys哈希环
		for i := 0; i < m.replicas; i++ {
			hash := int(m.hash([]byte(strconv.Itoa(i) + key)))
			m.keys = append(m.keys, hash)
			m.hashMap[hash] = key
		}
	}

	sort.Ints(m.keys)
}

// 选择节点的Get方法
func (m *Map) Get(key string) string {
	if len(m.keys) == 0 {
		return ""
	}

	hash := int(m.hash([]byte(key)))

	// 在哈希环上搜索节点
	idx := sort.Search(len(m.keys), func(i int) bool {
		return m.keys[i] >= hash
	})

	return m.hashMap[m.keys[idx%len(m.keys)]]
}
